// greedy
// from left to right traverse num_str, last[d]=index, d is digit of num
// calculate last array, at most switch once.
import "strconv"

func maximumSwap(num int) int {
	num_str := strconv.Itoa(num)
	last := [10]int{0}
	for i, r := range num_str {
		last[r-'0'] = i
	}

	for i := 0; i < len(num_str); i++ {
		for d := 9; d > int(num_str[i]-'0'); d-- {
			if last[d] > i {
				return swap(num_str, i, last[d])
			}
		}
	}

	return num
}

func swap(num_str string, i, j int) int {
	num_rune := []rune(num_str)
	num_rune[i], num_rune[j] = num_rune[j], num_rune[i]
	num_str = string(num_rune)
	res, _ := strconv.Atoi(num_str)
	return res
}